Developer CD Series 1998 November: Tool Chest/Dev.CD Nov 98 TC.toast/Sample Code/Networking/ListMania1.0d1/ListMania.c

Text File | 1997-07-31 | 11.1 KB | 373 lines | [TEXT/CWIE]

/*
    File:        ListMania.c

    Contains:    Sample for demonstrating use of OT list utilities.

    Written by:    Quinn "The Eskimo!"

    Copyright:    © 1997 by Apple Computer, Inc., all rights reserved.

    Change History (most recent first):

    You may incorporate this sample code into your applications without
    restriction, though the sample code has been provided "AS IS" and the
    responsibility for its operation is 100% yours.  However, what you are
    not permitted to do is to redistribute the source as "DSC Sample Code"
    after having made changes. If you're going to re-distribute the source,
    we require that you make it clear in the source that the code was
    descended from Apple Sample Code, but that you've made changes.
*/

/////////////////////////////////////////////////////////////////////
// The OT debugging macros in <OTDebug.h> require this variable to
// be set.

#ifndef qDebug
#define qDebug    1
#endif

/////////////////////////////////////////////////////////////////////
// Pick up all the standard OT stuff.

#include <OpenTransport.h>

/////////////////////////////////////////////////////////////////////
// Pick up the OTDebugBreak and OTAssert macros.

#include <OTDebug.h>

/////////////////////////////////////////////////////////////////////
// Standard C prototypes.

#include <stdio.h>

/////////////////////////////////////////////////////////////////////
// OTDebugStr is not defined in any OT header files, but it is
// exported by the libraries, so we define the prototype here.

extern pascal void OTDebugStr(const char* str);

/////////////////////////////////////////////////////////////////////

// Notes
// -----
// This sample is designed to illustrate the use of the OT link-list
// routines in a simple producer/consumer environment.  The objects
// being produced and consumed are widgets, as defined by the Widget
// data type.  There are two key routines: ProduceWidgets and
// ConsumeWidgets.  The first routine produces widgets (either by
// reusing previously consumed (ie free) widgets, or by creating new
// ones) and puts them on a 'pending' list.  The second consumes the
// widgets by grabbing them off the pending list.  After consuming
// the widget (in this sample, "consumption" means merely printing
// to stdout), the routine returns the widget to a free list.
//
// This sample uses OTLIFO routines throughout.  OTLIFO routines
// are atomic with respect to interrupts, threads, and (most probably
// even MP tasks), and are faster than the standard Mac OS equivalents
// (ie Enqueue/Dequeue).
//
// In this sample, all the code is running at SystemTask time, however
// all the list management in the critical portions of the code
// (ie ProduceWidgets and ConsumeWidgets) is perfectly safe to run
// at interrupt time.  [ConsumeWidgets is not interrupt safe at the
// moment because it uses "printf", but you can make it interrupt safe
// if your definition of "consumption" is interrupt safe.]
//
// Another advantage of the OT list management routines is that they
// support putting elements on multiple different lists simultaneously.
// For example, all widgets are on the "list of all the widgets
// in the system" and one of either the free list or the pending list.
// OT's list management makes this very easy to do.

/////////////////////////////////////////////////////////////////////

// The Widget data structure holds all the information for a widget
// object.  This includes:
//
// o fSequenceNumber -- A unique, monotonically increasing, sequence
//   number for each widget that is ever created.
// o fCreationTime -- The time at which the widget was created.
// o fLastProducedTime -- The time at which the widget was last produced.
//
// The data structure also holds two link fields.  The first, fNext,
// is used to link together all the elements on either the pending
// or free widget lists.  The second link field is used to link all
// of the widgets together in one long list, regardless of what their
// status is.

struct Widget {
    OTLink         fNext;
    OTLink         fAllWidgets;

    UInt32      fSequenceNumber;
    OTTimeStamp fCreationTime;
    OTTimeStamp fLastProducedTime;
};
typedef struct Widget Widget, *WidgetPtr;

// The following three lists are used to hold lists of widgets.
// gAllWidgetList is the list of all the widgets in the system.
// gPendingWidgetList is the list of all the widgets that have
// been produced and are awaiting consumption.  gFreeWidgetList
// is the list of all the widgets that are available for reuse
// by the producer.
//
// A widget is always on the the gAllWidgetList (through its
// fAllWidgets link) and is either on the gPendingWidgetList
// or the gFreeWidgetList (through its fNext link).

static OTLIFO gAllWidgetList;
static OTLIFO gPendingWidgetList;
static OTLIFO gFreeWidgetList;

// gLastWidgetSequenceNumber holds the sequence number of the
// last widget that was produced.  When we produce a new widget,
// we add one to this number to get the sequence number for the
// new widget.

static UInt32 gLastWidgetSequenceNumber;

/////////////////////////////////////////////////////////////////////

static void InitWidgetLists(void)
    // Initialises all of the widget lists to empty.
{
    gAllWidgetList.fHead = nil;
    gPendingWidgetList.fHead = nil;
    gFreeWidgetList.fHead = nil;
    gLastWidgetSequenceNumber = 0;
}

static WidgetPtr CreateWidget(void)
    // This routine creates a new widget and returns it to the
    // caller.  The new widget is always added to the gAllWidgetList
    // through its fAllWidgets link, but is available to be linked to
    // another list through its fNext link.
{
    WidgetPtr result;

    // Allocate the memory for the widget.

    result = OTAllocMem(sizeof(Widget));
    OTAssert("CreateWidget: Could not create widget", result != nil);

    // Fill out the information fields of the widget.  Note the
    // use of OTAtomicAdd32 to increment gLastWidgetSequenceNumber
    // atomically.  This guarantees that the sequence number is
    // unique, even if this routine is re-entered.

    OTMemzero(result, sizeof(Widget));
    result->fSequenceNumber = OTAtomicAdd32(1, (long *) &gLastWidgetSequenceNumber);
    OTGetTimeStamp(&result->fCreationTime);

    // Add the widget to the list of all the widgets in the system.

    OTLIFOEnqueue(&gAllWidgetList, (OTLink *) &result->fAllWidgets);

    return (result);
}

static void ProduceWidgets(UInt32 howMany)
    // This routine produces howMany widgets and adds them
    // to the gPendingWidgetList.
{
    UInt32 i;
    OTLink *freeLink;
    WidgetPtr thisWidget;

    // Produce each new element in turn.

    for (i = 0; i < howMany; i++) {

        // Grab a free element off the front of the gFreeWidgetList.
        // If that returns nil, there is no free element and we have
        // to create a new widget.  Otherwise, use OTGetLinkObject
        // to derive thisWidget from freeLink.

        freeLink = OTLIFODequeue(&gFreeWidgetList);
        if ( freeLink != nil ) {
            thisWidget = OTGetLinkObject(freeLink, Widget, fNext);
        } else {
            thisWidget = CreateWidget();
        }

        // At this point thisWidget points to a free widget that is
        // not on the gFreeWidgetList.  We now produce the widget, which in
        // this sample merely involves setting fLastProducedTime.

        OTGetTimeStamp(&thisWidget->fLastProducedTime);

        // Now add the widget to the list of produced widgets.

        OTLIFOEnqueue(&gPendingWidgetList, (OTLink *) &thisWidget->fNext);
    }
}

static void PrintWidget(WidgetPtr thisWidget)
    // Prints a widget to stdout.
{
    printf("  %03d, Created @ %08x%08x, Produced @ %08x%08x",
        thisWidget->fSequenceNumber,
        thisWidget->fCreationTime.hi, thisWidget->fCreationTime.lo,
        thisWidget->fLastProducedTime.hi, thisWidget->fLastProducedTime.lo
        );
}

static void ConsumeWidgets(void)
    // This routine consumes all of the widgets that have been produced.
{
    OTLink *listToConsume;
    WidgetPtr thisWidget;

    // First start by atomically stealing the list of pending
    // widgets.  This removes all of the widgets on gPendingWidgetList
    // and returns them to us in listToConsume.  Then, reverse
    // the list so that we consume them in the same order they
    // were produced.
    //
    // Note that these two API routines are defined to deal with
    // the empty list case correctly, so we don't have to
    // explicitly test it ourselves.

    listToConsume = OTLIFOStealList(&gPendingWidgetList);
    listToConsume = OTReverseList(listToConsume);

    while ( listToConsume != nil ) {

        // Given the link element, derive the actual widget object.

        thisWidget = OTGetLinkObject(listToConsume, Widget, fNext);

        // Now consume the widget.  In this sample, consuming
        // a widget merely involves printing it to stdout.

        PrintWidget(thisWidget);
        printf("\n");

        // Move along to the next list element...

        listToConsume = listToConsume->fNext;

        // ... and enqueue the most recently consumed widget on
        // the list of free widgets.  Note that the order of these
        // two operations is important, because thisWidget->fNext
        // is the same memory location as listToConsume->fNext, so
        // we can't change thisWidget->fNext (by enqueuing it)
        // until we have extracted the linkage information from it.

        OTLIFOEnqueue(&gFreeWidgetList, (OTLink *) &thisWidget->fNext);
    }
}

static void DumpWidgetList(OTLIFO *list)
    // Dump a widget list that is linked using the fNext field.
    // This is appropriate for the pending and free lists of widgets.
{
    OTLink *link;
    WidgetPtr thisWidget;

    link = list->fHead;
    while ( link != nil ) {
        thisWidget = OTGetLinkObject(link, Widget, fNext);
        PrintWidget(thisWidget);
        printf("\n");
        link = link->fNext;
    }
}

static void DumpWidgetAllLists(void)
    // Dump each af the three global lists.
{
    OTLink *link;
    WidgetPtr thisWidget;

    printf("gPendingWidgetList\n");
    DumpWidgetList(&gPendingWidgetList);

    printf("gFreeWidgetList\n");
    DumpWidgetList(&gFreeWidgetList);

    printf("gAllWidgetList\n");

    link = gAllWidgetList.fHead;
    while ( link != nil ) {
        thisWidget = OTGetLinkObject(link, Widget, fAllWidgets);
        PrintWidget(thisWidget);
        printf("\n");
        link = link->fNext;
    }
}

/////////////////////////////////////////////////////////////////////

void main(void)
    // A simple command line shell for testing the various
    // routines defined above.
{
    OSStatus err;
    Boolean quitNow;
    char commandString[256];

    printf("Hello Cruel World!\n");

    err = InitOpenTransport();

    if (err == noErr) {

        InitWidgetLists();

        printf("Enter a command:\n");
        printf("p) Produce 3 widgets\n");
        printf("P) Produce 5 widgets\n");
        printf("c) Consume all pending widgets\n");
        printf("d) Dump all widget lists\n");
        printf("q) Quit\n");
        printf("\n");

        quitNow = false;
        do {
            printf("Enter a command:\n");
            gets(commandString);
            switch( commandString[0] ) {
                case 'q':
                case 'Q':
                    quitNow = true;
                    break;

                case 'c':
                case 'C':
                    ConsumeWidgets();
                    break;

                case 'p':
                    ProduceWidgets(3);
                    break;
                case 'P':
                    ProduceWidgets(5);
                    break;

                case 'd':
                case 'D':
                    DumpWidgetAllLists();
                    break;

                default:
                    printf("Don't understand “%s”.");
                    break;
            }
        } while ( ! quitNow );

        CloseOpenTransport();
    }

    if (err == noErr) {
        printf("Success.\n");
    } else {
        printf("Failed with error %d.\n", err);
    }
    printf("Done.  Press command-Q to Quit.\n");
}